The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Increasingly, public and private communications networks are being built and expanded using various packet technologies, such as Internet Protocol (IP).
A network device, such as a switch or router, typically receives, processes, and forwards or discards a packet based on one or more criteria, including the type of protocol used by the packet, addresses of the packet (e.g., source, destination, group), and type or quality of service requested. Additionally, one or more security operations are typically performed on each packet. But before these operations can be performed, a packet classification operation must typically be performed on the packet.
Packet classification as required for, inter alia, access control lists (ACLs) and forwarding decisions, is a demanding part of switch and router design. The packet classification of a received packet is increasingly becoming more difficult due to ever increasing packet rates and number of packet classifications. For example, ACLs require matching packets on a subset of fields of the packet flow label, with the semantics of a sequential search through the ACL rules. IP forwarding requires a longest prefix match.
Known approaches of packet classification include using custom application-specific integrated circuits (ASICs), custom circuitry, software or firmware controlled processors, binary and ternary content-addressable memories (CAMs). The use of programmable software or firmware have advantages as they provide some level of flexibility, which becomes especially important as new protocols and services are added to existing network. Customer typically desire to use their existing hardware (e.g., routers, switches etc.) to support these new protocols and services. However, known software and firmware implementations are relatively slow, and typically place a performance bound which may be incompatible with new requirements. CAMs are increasingly being used in packet classification especially because of their performance. However, these content-addressable memories are typically expensive in terms of power consumption and space, and are limited in the size of an input word (e.g., 72, 144, etc.) on which a lookup operation is performed.
Various applications that use packet classification, such as Security Access Control, Quality of Service etc., typically need to match source and/or destination addresses. These addresses can be quite large, and possibly too large for providing all bits representing one or more addresses to a content-addressable memory. For example, Internet Protocol version 6 (IPv6) uses addresses having a length of 128 bits and a typical large content-addressable memory has a maximum search width of 288 bits. Therefore, almost all the bits of a content-addressable memory would be used for matching the source and destination addresses, while providing a small, and quite possibly insufficient number of input bits for matching other criteria such as source and destination port numbers, protocol and other header fields, etc.
One known approach for providing lookup capability when the size of information to be matched exceeds the lookup word size of a CAM is to use multiple CAMs to perform multiple lookups in parallel, and then merging the multiple lookup results. However, such a result requires the use of multiple CAMs.
Another known approach uses a single CAM and breaks the desired lookup string into different segments and performs multiple lookups. A CAM is programmed with parent entries (i.e., those for matching a first segment) and child entries (e.g, those for matching the remaining segments), wherein each child entry includes the address of its parent as part of its lookup string to ensure that only children entries of a matched parent entry are matched. Additionally, child and parent entries contain a different two bit tag to ensure a child entry is not matched when a parent entry is desired, and vice versa. A first segment of the string is provided as input to the CAM to produce a matching address (e.g., page and word address). A lookup word including a second segment of the string along with the matching address and child tagging is then provided as input to the CAM to produce a second matching address. This process can be repeated wherein the child entry becomes the parent entry for another child entry. This approach uses a single CAM, however, the use of the address of a parent entry as the prefix for a lookup of a child entry is inflexible, and typically requires a fixed number of bits which may be excessive.
Another known approach extending the comparand width as long as desired using only one CAM concatenates adjacent entries using validity bits to identify successive entries. A first entry in a long comparand is stored as Valid, but the succeeding entries in that comparand are stored as RAM-only. If a match is found, the Status register is examined to find the match address and whether multiple matches exist. Then, the contents of the memory at the match location +1 are read out, and an external compare is performed against the next portion of the unknown. If a match is found, the contents of the memory at the match location +2 can be read out, and another compare executed. If a match is not found in these external compares, the match location in the CAM can be set to “SKIP” and a CMP V command issued to the CAM to find the next matching location, and the external compare process continued until a match is found with the entire unknown. After completion, the “SKIPPED” entries are returned to “VALID.”
Another single CAM approach tags each succeeding stored entry in a long comparand with its sequence number. The first entry is tagged “1”, the second entry tagged “2”, the third entry is tagged “3”, and so forth. After the first match is found, the second portion of the unknown is entered into the comparand register along with the tag for “2”, and if a match is found, the Status register is examined to see if the match address is equal to the previous match address +1. If it is, then the third portion of the unknown can be loaded into the comparand with the tag for “3”, and so forth. If the match address is not an increment from the previous address, that means the mach has failed, and the fist matching location should be set to “SKIP” and a CMP V issued to find the next higher match. Such approaches may have bad performance and may be difficult to implement.
Needed are new methods and apparatus for performing lookup operations using content-addressable memories and other devices, especially when the desired lookup string is longer than that allowed by a single lookup option on a particular CAM.